1. Field of the Invention
This invention relates generally to memory management. More particularly, an embodiment of the present invention relates to integration of mark bits and allocation bits in garbage collectors.
2. Description of Related Art
Memory management-related problems, such as memory waste, are fairly common in modern computer systems. Such problems often lead to other problems, including excessive memory usage, performance loss, and even application failures in the computer system. To reduce such memory management-related problems, most computer systems employ garbage collection.
Garbage collection typically involves a software routine to search memory for space of unused data and to reclaim and use such space for the general memory pool called the heap. The heap refers to a common pool of memory that is available to the program. Managing the heap is typically done by allocation and deallocation of memory for objects within the heap. Many computer systems employ mark-sweep based garbage collectors 100, such as the one illustrated in FIG. 1A.
The mark-sweep based garbage collector (garbage collector) 100 includes a heap 102 and adopts mark-sweep algorithm requiring a relatively large space for a set of mark bits (or M bits) 104 having mark bits 106-108. Typically, a mark bit 106-108 is proportional to approximately 4 bytes of an object 110-112 of the heap 102. However, the mark bits 106-108 only coincidently refer to the objects 110-112 of the heap 102. To help solve this problem by clarifying whether an integer value does refer to a legitimate or living object 110-112, a mark-sweep based conservative garbage collector (conservative garbage collector) 120, as illustrated in FIG. 1B, is implemented. A conservative garbage collector 120 employs a set of allocation bits (or A bits) 122, in addition to having a set of mark bits 104. Typically, an allocation bit 124-126 is proportional to about 4 bytes of an object 110-112 in the heap 102. The allocation bits 124-126 are used to correspond to addresses of the objects 110-112 contained in the heap 102 to help identify the objects 110-112 and avoid spurious pointers.
Stated differently, in a conservative garbage collector 120, an allocation bits set 122, having allocation bits 124-126, is added to dynamically record addresses of the living objects 110-112. However, the dynamic recording of the addresses using the conservative garbage collector 120 requires maintaining an extra space for each of the allocation bits 124-126 at a relatively high runtime computing cost. The term “conservatism” refers to the conservative garbage collector 120 being conservative in treating integer values on the stack or in the heap 102 or other areas, such as registers, as spurious pointers.
The conservative garbage collector 120, bundled with the garbage collector 100, is a frequently deployed system today to simplify runtime design. However, the design dilemma to employ both the mark-sweep based algorithm and conservative features is overwhelming for most systems, particularly for small systems. The extra space and time overhead of having both the mark-bits 106-108 and the allocation-bits 124-126 is undesirable for small systems and for most systems with limited memory and computation power.